package 队列;

import com.alibaba.fastjson.JSON;
import javafx.util.Pair;

import java.util.*;

public class No347前K个高频元素 {

    /**
     * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
     *
     * 示例 1:
     * 输入: nums = [1,1,1,2,2,3], k = 2
     * 输出: [1,2]
     * 示例 2:
     * 输入: nums = [1], k = 1
     * 输出: [1]
     */

    public static int[] topKFrequent(int nums[],int k){

        Map<Integer,Pair<Integer,Integer>> map=new HashMap<>();

        for (int num : nums) {
            Pair<Integer, Integer> pair = map.get(num);
            if(pair==null){
                map.put(num,new Pair<>(num,1));
            }else{
                map.put(num,new Pair<>(num,pair.getValue()+1));
            }
        }

        PriorityQueue<Pair<Integer,Integer>> priorityQueue=
                new PriorityQueue<>((p1,p2)->p1.getValue()-p2.getValue());

        for (Integer integer : map.keySet()) {
            Pair<Integer, Integer> pair = map.get(integer);
            priorityQueue.add(pair);
            if(priorityQueue.size()>k)
                priorityQueue.poll();
        }

        int[] result=new int[priorityQueue.size()];
        int i=result.length-1;
        while (!priorityQueue.isEmpty()){
            result[i--]=priorityQueue.poll().getKey();
        }

        return result;
    }

    public static void main(String[] args) {
        int[] ints = topKFrequent(new int[]{1, 1, 4, 4, 4, 4, 1, 3}, 2);
        System.out.println(JSON.toJSONString(ints));
    }

}
